package leetcode.code1799;

public class Solution {

	int[] nums;
	int[][] gcds;
	int nn;

	public int maxScore(int[] nums) {
		nn = nums.length;
		int n = nn >> 1;
		this.nums = nums;
		gcds = new int[nn][nn];
		for (int i = 0; i < nn; i++) {
			for (int j = i + 1; j < nn; j++) {
				int gcd = gcd(nums[i], nums[j]);
				gcds[i][j] = gcd;
			}
		}
		int limit = (1 << nn) - 1;
		Integer[] dp = new Integer[1 << nn];
		return f(limit, n, dp);
	}

	private int f(int limit, int n, Integer[] dp) {
		if (n == 0) {
			return 0;
		}
		if (dp[limit] != null) {
			return dp[limit];
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < nn; i++) {
			if (((1 << i) & limit) != 0) {
				for (int j = i + 1; j < nn; j++) {
					if (((1 << j) & limit) != 0) {
						int cur = n * gcds[i][j];
						max = Math.max(max, cur + f(limit ^ (1 << i) ^ (1 << j), n - 1, dp));
					}
				}
			}
		}
		dp[limit] = max;
		return max;
	}

	public int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

}
